package 中等.链表;

import util.ListNode;

/**
 * 给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
 * <p>
 * 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
 * <p>
 * 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/delete-the-middle-node-of-a-linked-list
 */
public class 删除链表的中间节点_5943 {

    private int down;

    private int up;

    public static void main(String[] args) {

        ListNode head = new ListNode(1);
        ListNode cur = head;
        System.out.println(cur + "-" + cur.val);
        System.out.println(head + "-" + head.val);
        System.out.println(cur == head);

        //cur存放的是地址值
        //cur=cur.next，其实是将cur的下个节点的地址值赋值给cur变量
        //然而head这个变量存放的是头节点的地址值，不会改变
        cur.val = 2;
        System.out.println(cur + "-" + cur.val);
        System.out.println(head + "-" + head.val);
        System.out.println(cur == head);
        //cur和head引用的是同一个对象，所以cur改变，head也会改变

    }

    /**
     * 快慢指针
     *
     * @param head
     * @return
     */
    public ListNode efficientDeleteMiddle(ListNode head) {

        ListNode low = head;
        ListNode quick = head;

        while (quick != null && quick.next != null) {
            low = low.next;
            quick = quick.next.next;
        }

        low.val = low.next.val;
        low.next = low.next.next;

        return head;
    }

    /**
     * 递归
     *
     * @param head
     * @return
     */
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {  //只有一个元素
            return null;
        }
        if (head.next.next == null) {  //只有两个元素
            head.next = null;
            return head;
        }
        operateMiddle(head);
        return head;
    }

    private void operateMiddle(ListNode head) {
        if (head == null) {
            return;
        }
        down++;
        operateMiddle(head.next);
        up++;
        if (down / 2 == down - up) {  //找到中间节点
            //将后一个节点替换掉当前的中间节点
            head.val = head.next.val;
            head.next = head.next.next;
        }
    }

}
